﻿ #define _CRT_SECURE_NO_WARNINGS 1

 class Solution
 {
	 typedef pair<string, int> PSI;
	
		 struct cmp
		 {
		 bool operator()(const PSI & a, const PSI & b)
			 {
			 if (a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列
				 {
				 return a.first < b.first;
				 }
			 return a.second > b.second;
			 }
		 };
	
 public:
	 vector<string> topKFrequent(vector<string>&words, int k)
		 {
		 // 1. 统计⼀下每⼀个单词的频次
			 unordered_map<string, int> hash;
		 for (auto& s : words) hash[s]++;
		
			 // 2. 创建⼀个⼤⼩为 k 的堆
			 priority_queue<PSI, vector<PSI>, cmp> heap;
		
			 // 3. TopK 的主逻辑
			 for (auto& psi : hash)
			 {
			 heap.push(psi);
			 if (heap.size() > k) heap.pop();
			 }
		
			 // 4. 提取结果
			 vector<string> ret(k);
		 for (int i = k - 1; i >= 0; i--)
			 {
			 ret[i] = heap.top().first;
			 heap.pop();
			 }
		 return ret;
		 }
	 };